package Fundamental.sort;

import java.util.Arrays;

public class QuikSort {
    public static void main(String[] args) {
        int[] A1 = {4 , 6 , 1 , 8 , 3 , -1};
        int[] A2 = { 9 , 17 , 34 , 22 , 90};
        int[] merge = {4 , 6 , 1 , 8 , 3 , -1 , 9 , 17 , 34 , -33 , 1 ,  22 , 90 , -100};
        sort(merge , 0 , merge.length - 1);
        System.out.println(Arrays.toString(merge));;
    }
    public static void swap(int[] array , int from , int to){
        int temp = array[from];
        array[from] = array[to];
        array[to] = temp ;
    }
    public static void sort(int[] array , int from , int to){
         if(from >= to){
             return;
         }
         int i = from + 1;
         int j = to ;
         int key = array[from];
         while(i < j){
             // 从左到右找到第一比 key 小的
             while(key <= array[j] && j > i){
                 j--;
             }
             // 从右到左第一个比 key 大的
             while(key > array[i] && j > i){
                i++;
             }
             if(i<j){
                 swap(array , i , j);
                 i++;
                 j--;
             }
         }
         if(array[i] <= key){
           swap(array , from , i);
         }else{
             swap(array , from , i -1);
         }
         // 接收为 i -1  i 的位置其实有序了，不需要移动了，所以不需要参与到下次的排序了。
         sort(array , from , i - 1 );
         // 同理，开始的位置事 i+1
         sort(array , i+1 , to);
    }
}
